package graph;

import java.util.*;

/**
 * 卡110.字符串接龙
 * 题目描述
 * 字典 strList 中从字符串 beginStr 和 endStr 的转换序列是一个按下述规格形成的序列：
 * 1. 序列中第一个字符串是 beginStr。
 * 2. 序列中最后一个字符串是 endStr。
 * 3. 每次转换只能改变一个字符。
 * 4. 转换过程中的中间字符串必须是字典 strList 中的字符串，且strList里的每个字符串只用使用一次。
 * 给你两个字符串 beginStr 和 endStr 和一个字典 strList，找到从 beginStr 到 endStr 的最短转换序列中的字符串数目。如果不存在这样的转换序列，返回 0。
 * 输入描述
 * 第一行包含一个整数 N，表示字典 strList 中的字符串数量。 第二行包含两个字符串，用空格隔开，分别代表 beginStr 和 endStr。 后续 N 行，每行一个字符串，代表 strList 中的字符串。
 * 输出描述
 * 输出一个整数，代表从 beginStr 转换到 endStr 需要的最短转换序列中的字符串数量。如果不存在这样的转换序列，则输出 0。
 *
 * 相当于begin和end为起点和终点，找到一条从起点到终点的最短路径，中间部分就是wordlist，且路径上每次只能改变一个单词
 */

/**
 * 一刷
 */
public class str {
    public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 使用set作为查询容器，效率更高
        HashSet<String> set = new HashSet<>(wordList);

        // 声明一个queue存储每次变更一个字符得到的且存在于容器中的新字符串
        Queue<String> queue = new LinkedList<>();

        // 声明一个hashMap存储遍历到的字符串以及所走过的路径path
        HashMap<String, Integer> visitMap = new HashMap<>();
        queue.offer(beginWord);
        visitMap.put(beginWord, 1);

        while (!queue.isEmpty()) {
            String curWord = queue.poll();
            int path = visitMap.get(curWord);

            for (int i = 0; i < curWord.length(); i++) {
                char[] ch = curWord.toCharArray();
                // 每个位置尝试26个字母
                for (char k = 'a'; k <= 'z'; k++) {
                    ch[i] = k;

                    String newWord = new String(ch);
                    if (newWord.equals(endWord)) return path + 1;

                    // 如果这个新字符串存在于容器且之前未被访问到
                    if (set.contains(newWord) && !visitMap.containsKey(newWord)) {
                        visitMap.put(newWord, path + 1);
                        queue.offer(newWord);
                    }
                }
            }
        }

        return 0;
    }

    public static void main (String[] args) {
        /* code */
        // 接收输入
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        sc.nextLine();
        String[] strs = sc.nextLine().split(" ");

        List<String> wordList = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            wordList.add(sc.nextLine());
        }

        // wordList.add(strs[1]);

        // 打印结果
        int result = ladderLength(strs[0], strs[1], wordList);
        System.out.println(result);
    }
}
